import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: GaoBo
 * Date: 2021-07-22
 * Time: 9:36
 */
public class TestHeap {

    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }


    /**
     * 建大堆
     * @param array
     */
    public void createHeap(int[] array) {

        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }

        //parent 就代表每颗子树的根节点
        for(int parent = (array.length-1-1)/2;parent >= 0;parent--) {
            //第2个参数  每次调整的结束位置应该是：this.usedSize.
            adjustDown(parent,this.usedSize);
        }
    }

    public void adjustDown(int root,int len) {
        int parent = root;
        int child = 2*parent+1;
        while(child < len) {
            //找到左右孩子的最大值
            //1、前提是你得有右孩子
            if(child+1 < len && this.elem[child] < this.elem[child+1]) {
                child++;
            }
            //保证，child下标的数据  一定是左右孩子的最大值的下标
            if(this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    public void adjustUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if(this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[parent];
                this.elem[parent] = this.elem[child];
                this.elem[child] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

    public void push(int val) {
        if(isFull()) {
            //扩容
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;//10
        this.usedSize++;//11
        adjustUp(this.usedSize-1);//10下标
    }

    public boolean isFull() {
        return this.usedSize == this.elem.length;
    }
    public void pop() {
        if(isEmpty()) {
            return;
        }
        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.usedSize-1];
        this.elem[this.usedSize-1] = tmp;
        this.usedSize--;//9 删除了
        adjustDown(0,this.usedSize);
    }
    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    public int peek() {
        if(isEmpty()) {
           throw new RuntimeException("队列为空");
        }
        return this.elem[0];
    }

    /**
     * 一定是先创建大堆
     *      调整每棵树
     * 开始堆排序：
     *     先交换  后调整  直到 0下标
     */
    public void heapSort() {
        int end = this.usedSize-1;
        while(end > 0) {
            int tmp = this.elem[0];
            this.elem[0] =this.elem[end];
            this.elem[end] = tmp;
            adjustDown(0,end);
            end--;
        }
    }
}
